package swap

/*
冒泡排序（bubblesort）通过连续地比较与交换相邻元素实现排序。这个过程就像气泡从底部升到顶部一样，
因此得名冒泡排序。
冒泡过程可以利用元素交换操作来模拟：从数组最左端开始向右遍历，依次比较相邻元素大
小，如果“左元素>右元素”就交换二者。遍历完成后，最大的元素会被移动到数组的最右端。
*/
/* 冒泡排序 */
func bubbleSort(nums []int) {
	// 外循环：未排序区间为 [0, i]`
	for i := len(nums) - 1; i > 0; i-- {
		// 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
		for j := 0; j < i; j++ {
			if nums[j] > nums[j+1] {
				// 交换 nums[j] 与 nums[j + 1]
				nums[j], nums[j+1] = nums[j+1], nums[j]
			}
		}
	}
}

/* 冒泡排序（标志优化）*/
func bubbleSortWithFlag(nums []int) {
	// 外循环：未排序区间为 [0, i]
	for i := len(nums) - 1; i > 0; i-- {
		flag := false // 初始化标志位
		// 内循环：将未排序区间 [0, i] 中的最大元素交换至该区间的最右端
		for j := 0; j < i; j++ {
			if nums[j] > nums[j+1] {
				// 交换 nums[j] 与 nums[j + 1]
				nums[j], nums[j+1] = nums[j+1], nums[j]
				flag = true // 记录交换元素
			}
		}
		if flag == false { // 此轮“冒泡”未交换任何元素，直接跳出
			break
		}
	}
}

// 將最小值移動至最左邊

func bubbleSortIpp(arr []int) {
	length := len(arr) - 1
	for i := 0; i < length; i++ {
		for j := 0; j < length-i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
}
func bubbleSortFlagIpp(arr []int) {
	length := len(arr)
	for i := 0; i < length; i++ {
		flag := false // 初始化标志位
		for j := 0; j < length-1-i; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
				flag = true // 初始化标志位

			}
		}
		if flag == false { // 此轮“冒泡”未交换任何元素，直接跳出
			break
		}
	}
}
